package Queue;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 题目 ：最大队列
 * 题目详述 ：
 * 请定义一个队列并实现函数 max_value 得到队列里的最大值，
 * 要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
 * 若队列为空，pop_front 和 max_value需要返回 -1
 *
 */
public class MaxQueue {
    /**
     *  核心思想 ：
     *  即，使用队列 + 双端队列（用来存放队列中的最大元素）
     *  （1）队列 a ：用来保存队列中的元素
     *  （2）双端队列 b ：即，用来保存队列中的最大元素
     *  （若是双端队列之前的值小于所要插入的值，即需要将较小的值先进行弹出队列，直至队列尾部的元素大于或者等于所要插入的值）
     */
    Queue<Integer> queue; // 队列，用于存放队列元素
    Deque<Integer> deque; // 双端队列，用于存放队列中最大元素
    public MaxQueue() {
        queue = new LinkedList<>();
        deque = new LinkedList<>();
    }

    public int max_value() {
        // 若是双端队列为空,返回值为-1
        if(deque.isEmpty()){
            return -1;
        }
//        System.out.println(deque.peek());
        return deque.peek();
    }

    public void push_back(int value) {
        queue.offer(value);
        // 给队列插入值时，若是双端队列为空，即代表了之前的queue也是空的；
        while (!deque.isEmpty() && deque.peekLast() < value){
            /**
             * 注意 ：
             *  即，若是双端队列（存放原本队列中最大值）的队尾元素小于插入的元素，
             *  ===》 即，代表了当双端队列前面的元素全部 出队列后，队列中的最大元素即为刚刚插入的元素；
             *  即，queue中的区间 [deque中上一个最大值 ， value] 的最大值为 value；
             */
            deque.pollLast();
        }
        deque.offer(value);  // 需要将队列中的元素插入deque中
        System.out.println(deque.peekLast());
    }

    public int pop_front() {
        // 若是队列为空的1话，即不存在将元素弹出队列
        if (queue.isEmpty()){
            return -1;
        }
        /**
        注意 ：
         需要注意 java中的（1）基本类型和（2）基本类型包装类 之间的区别 ！！！
         */
        Integer deleteFirst = queue.poll();
        System.out.println("queue所删除的队首元素 ：" + deleteFirst);
        System.out.println("deque的队首元素 ： " + deque.peekFirst());
        if(deleteFirst.compareTo(deque.peekFirst()) == 0){
            // 若是队列中所弹出的队首元素 == 双端队列中队首元素（代表的是，此时队列最大值）
            // 即，同时也需要去将双端队列中的队首元素弹出
            System.out.println("所删除的双端队列元素 ：" + deque.pollFirst());
            System.out.println("剩下的双端队列首元素 : " + deque.peek());
        }
        return deleteFirst;
    }


    // 注意 ：算法需要进行优化，此时使用的算法时间复杂度和空间复杂度都很高
}
